#include "template.h"
/* 二叉指数树（Fenwick Tree）模板类 */
template <typename T>
struct FenwickTree {
    /* 树的大小 */
    int n;
    /* 存储树的数组，a[i]表示从下标0到i的累计值 */
    std::vector<T> a;
    /* 构造函数，初始化树 */
    FenwickTree(int n_ = 0) {
        init(n_);
    }
    /* 初始化树的大小 */
    void init(int n_) {
        n = n_;
        /* 初始化数组，确保所有位置的值为0 */
        a.assign(n, T{});
    }
    /* 向下更新，将值v添加到下标x处 */
    void add(int x, const T &v) {
        /* 通过位运算向上更新 */
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    /* 向上查询，返回下标x处的累计值 */
    T sum(int x) {
        /* 初始化结果 */
        T ans{};
        /* 通过位运算向下查询 */
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    /* 查询区间[l, r]的累计和 */
    T rangeSum(int l, int r) {
        /* 返回r处的累计值减去l处的累计值 */
        return sum(r) - sum(l);
    }
    /* 查找第一个大于等于k的值的下标 */
    int select(const T &k) {
        /* 初始化结果 */
        int x = 0;
        /* 初始化当前累计值 */
        T cur{};
        /* 从最高位开始遍历 */
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            /* 如果当前位置加i仍在范围内，并且当前累计值加a[x+i-1]小于等于k */
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                /* 更新x为x加上i */
                x += i;
                /* 更新当前累计值 */
                cur = cur + a[x - 1];
            }
        }
        /* 返回结果 */
        return x;
    }
};
